class Solution {
public:
    vector<string> generateParenthesis(int n)
    {
        vector<string> ans;
        string path;
        function<void(int)> dfs = [&](int i) {
            if (i == 2 * n)
            {
                int x = 0, y = 0;
                for (auto e : path)
                {
                    if (e == '(') x++;
                    else y++;
                    if (x < y) return;
                }
                if (x == y) ans.push_back(path);
                return;
            }
            path += '(';
            dfs(i + 1);
            path.pop_back();

            path += ')';
            dfs(i + 1);
            path.pop_back();
            };
        dfs(0);
        return ans;
    }
};